//You are given the root of a binary search tree (BST), where exactly two nodes
//of the tree were swapped by mistake. Recover the tree without changing its struc
//ture.
//
// Follow up: A solution using O(n) space is pretty straight forward. Could you
//devise a constant space solution?
//
//
// Example 1:
//
//
//Input: root = [1,3,null,null,2]
//Output: [3,1,null,null,2]
//Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 mak
//es the BST valid.
//
//
// Example 2:
//
//
//Input: root = [3,1,4,null,null,2]
//Output: [2,1,4,null,null,3]
//Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 a
//nd 3 makes the BST valid.
//
//
//
// Constraints:
//
//
// The number of nodes in the tree is in the range [2, 1000].
// -231 <= Node.val <= 231 - 1
//
// Related Topics 树 深度优先搜索
// 👍 478 👎 0


package leetcode.editor.cn;


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

//Java：Recover Binary Search Tree
class P99RecoverBinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new P99RecoverBinarySearchTree().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        List<Integer> list = new ArrayList<>();

        public void recoverTree(TreeNode root) {
            inOrder(root);
            findSwapVal(root);


        }

        public void inOrder(TreeNode root) {
            if (root != null) {
                inOrder(root.left);
                list.add(root.val);
                inOrder(root.right);
            }

        }

        public void findSwapVal(TreeNode root) {
            int len = list.size();
            int x = -1, y = -1;
            for (int i = 0; i < len - 1; i++) {
                if (list.get(i) == null) {
                    continue;
                }
                if (list.get(i) > list.get(i + 1)) {
                    y = list.get(i + 1);
                    if (x == -1) {
                        x = list.get(i);
                    } else {
                        break;
                    }
                }
            }
            recoverTree(root, x, y);
        }

        int count = 2;

        private void recoverTree(TreeNode root, int x, int y) {
            if (root == null) {
                return;
            }
            if (root.val == x || root.val == y) {
                root.val = root.val == x ? y : x;
                if (--count == 0) {
                    return;
                }
            }
            recoverTree(root.left, x, y);
            recoverTree(root.right, x, y);

        }

        //2.中序遍历
        public void recoverTreeMid(TreeNode root) {
            Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
            TreeNode x = null, y = null, pred = null;

            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                if (pred != null && root.val < pred.val) {
                    y = root;
                    if (x == null) {
                        x = pred;
                    } else {
                        break;
                    }
                }
                pred = root;
                root = root.right;
            }

            swap(x, y);
        }

        //Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 xx）：
        //
        //如果 xx 无左孩子，则访问 xx 的右孩子，即 x = x.\textit{right}x=x.right。
        //如果 xx 有左孩子，则找到 xx 左子树上最右的节点（即左子树中序遍历的最后一个节点，xx 在中序遍历中的前驱节点），我们记为 \textit{predecessor}predecessor。根据 \textit{predecessor}predecessor 的右孩子是否为空，进行如下操作。
        //如果 \textit{predecessor}predecessor 的右孩子为空，则将其右孩子指向 xx，然后访问 xx 的左孩子，即 x = x.\textit{left}x=x.left。
        //如果 \textit{predecessor}predecessor 的右孩子不为空，则此时其右孩子指向 xx，说明我们已经遍历完 xx 的左子树，我们将 \textit{predecessor}predecessor 的右孩子置空，然后访问 xx 的右孩子，即 x = x.\textit{right}x=x.right。
        //重复上述操作，直至访问完整棵树。
        //
        //作者：LeetCode-Solution
        //链接：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/
        //来源：力扣（LeetCode）
        //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
        public void recoverTreeMir(TreeNode root) {
            TreeNode x = null, y = null, pred = null, predecessor = null;

            while (root != null) {
                if (root.left != null) {
                    // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                    predecessor = root.left;
                    while (predecessor.right != null && predecessor.right != root) {
                        predecessor = predecessor.right;
                    }

                    // 让 predecessor 的右指针指向 root，继续遍历左子树
                    if (predecessor.right == null) {
                        predecessor.right = root;
                        root = root.left;
                    }
                    // 说明左子树已经访问完了，我们需要断开链接
                    else {
                        if (pred != null && root.val < pred.val) {
                            y = root;
                            if (x == null) {
                                x = pred;
                            }
                        }
                        pred = root;

                        predecessor.right = null;
                        root = root.right;
                    }
                }
                // 如果没有左孩子，则直接访问右孩子
                else {
                    if (pred != null && root.val < pred.val) {
                        y = root;
                        if (x == null) {
                            x = pred;
                        }
                    }
                    pred = root;
                    root = root.right;
                }
            }
            swap(x, y);
        }

        public void swap(TreeNode x, TreeNode y) {
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
